Newton's Method is an iterative method that has proven to be an effective way to solve for the roots of a polynomial equation. It is particularly attractive as a computational method in a high speed computer when the computer has a hardware floating point multiplier and a hardware floating point adder-subtractor.
In the above case, a hardware implementation of Newton's method can be used to rapidly compute the floating point reciprocal or floating point reciprocal square root of an unknown value C which in turn can be used to compute floating point divide or square root operations.
In general, the Newton's method solves F(x)=0 given that the function F(x) is defined and twice differentiable on the interval (a,b). The algorithm is given as: EQU x.sub.(m+1) =x.sub.m -F(x.sub.m)/F'(x.sub.m)
where: x.sub.0 =is an initial approximation for F(x)=0, x.sub.m =is the mth iteration,
x.sub.(m+1) =is the (m+1)st iteration, and
F'(x.sub.m)=is the first derivative of F() evaluated at x.sub.m.
Newton's Method for the specific case of determining reciprocal involves the solving: EQU F(x)=x.sup.-1 -C
and the Newton Iteration is given by: EQU x.sub.(m+1) =x.sub.m {2-cx.sub.m }
for F(x)=0, x.sup.-1 =c and x is equal to the reciprocal of C.
Prior state-of-the-art hardware implementations have revolved around decomposing each Newton Iteration into the following successive computations:
______________________________________ 1. cx.sub.m form the product of x.sub.m and C 2. {2 - cx.sub.m } subtract the product from 2 3. x.sub.m {2 - cx.sub.m } form the product ______________________________________
Each step requires only the use of a multiplier or an adder. Hence, each Newton Iteration requires three operations.
The improved method forms the Newton Iteration in the following two steps versus the three steps as in prior art:
______________________________________ 1. cx.sub.m form the product of x.sub.m and C 2. x.sub.m {2 - cx.sub.m } form the product and difference simultaneously. ______________________________________
Newton's Method for the specific case of determining reciprocal square roots involves solving: EQU F(x)=x.sup.-2 -C=0
and the Newton Iteration is given by: EQU x.sub.(m+1) =0.5x.sub.m {3-cx.sub.m.sup.2 }
for F(x)=0, x.sup.-2 =C and x is the reciprocal square root of C.
Prior state of the art hardware implementations have revolved around decomposing each Newton Iteration into the following successive computations:
______________________________________ 1. x.sub.m.sup.2 square x.sub.m 2. cx.sub.m.sup.2 multiply the square of x.sub.m by C 3. 3 - cx.sub.m.sup.2 subtract the product from 3 4. x.sub.m {3 - cx.sub.m.sup.2 } multiply the difference by x.sub.m 5. .5x.sub.m {3 - cx.sub.m.sup.2 } multiply the quantity by .5 ______________________________________
Each step requires only the use of a multiplier or an adder. Hence, each Newton Iteration requires five operations.
The improved method forms the Newton Iteration in the following three steps versus the five steps as in prior art:
______________________________________ 1. x.sub.m.sup.2 square x.sub.m 2. cx.sub.m.sup.2 multiply the square of x.sub.m by C 3. .5x.sub.m {3 - cx.sub.m.sup.2 } form the product and difference simultaneously. ______________________________________